package com.hqq.sort.merge;

import com.hqq.sort.Sort;

/**
 * MergeSort
 * 归并排序
 * 原理:
 * 把一个数组分成两半分别排序 然后将结果归并起来
 * 优点:
 * 保证任意长度为N的数组排序所需时间和NlogN成正比
 * 缺点:
 * 所需的空间和N成正比
 * Created by heqianqian on 2017/8/3.
 */
public class MergeSort extends Sort {

    private static Comparable[] aux;

    public static void sortUB(Comparable[] a) {
        aux = new Comparable[a.length];
        sortUB(a, 0, a.length - 1);
    }

    /**
     * 自顶向下的归并排序
     */
    private static void sortUB(Comparable[] a, int low, int high) {
        if (high <= low) {
            return;
        }
        int mid = low + (high - low) / 2;
        sortUB(a, low, mid);
        sortUB(a, mid + 1, high);
        merge(a, low, mid, high);
    }

    /**
     * 自底向上的归并排序
     */
    public static void sortBU(Comparable[] a) {
        int length = a.length;
        aux = new Comparable[length];
        for (int sz = 1; sz < length; sz = 2 * sz) {
            for (int lo = 0; lo < length - sz; lo += sz * 2) {
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, length - 1));
            }
        }
    }

    /**
     * 原地归并
     * 思想:
     * 把a[low]-a[mid]和a[mid+1]-a[high]两部分元素归并到aux数组中 再将aux中的值复制到a数组中
     */
    private static void merge(Comparable[] a, int low, int mid, int high) {
        int i = low, j = mid + 1;
        //使用中间数组
        for (int k = low; k <= high; k++) {
            aux[k] = a[k];//把a中的元素复到aux数组中
        }
        for (int k = low; k <= high; k++) {
            if (i > mid) {//左半边用完取右半边元素
                a[k] = aux[j++];
            } else if (j > high) {//右半边用完取左半边元素
                a[k] = aux[i++];
            } else if (less(aux[j], aux[i])) {
                //左半边的当前元素小于右半边的元素取右半边元素
                a[k] = aux[j++];
            } else {
                //右半边的当前元素小于左半边的元素取左半边元素
                a[k] = aux[i++];
            }
        }
    }
}
